<!DOCTYPE html>
<html lang="en">
    <head>
        <meta charset="UTF-8" />
        <meta name="viewport" content="width=device-width, initial-scale=1.0" />
        <title>Document</title>
    </head>
    <body>
        <script>
            /*
            思路：每个路径都是由左子树的最大路径+root.val+右子树的最大路径
            因此，我们需要计算左右子树的最大路径和，需要从叶子节点开始遍历，因此用后序遍历

            */
            var maxPathSum = function (root) {
                let maxSum = root.val
                function postOrder(root) {
                    if (!root) return 0
                    //获取左右节点的最大值
                    let leftSum = postOrder(root.left)
                    let rightSum = postOrder(root.right)
                    maxSum = Math.max(maxSum, leftSum + rightSum + root.val)
                    //当前节点也是作为子节点，但是得看是左+根 还是右+根  或者干脆不作为节点
                    let returnSum = Math.max(0, leftSum, rightSum) + root.val
                    return returnSum > 0 ? returnSum : 0
                }
                postOrder(root)
                return maxSum
            }
        </script>
    </body>
</html>
